package com.codepuzzler;

import java.util.ArrayList;
import java.util.List;

public class StringPermutations {
	public List<String> permutations(char[] str) {
		if (str.length == 1) {
			List<String> single = new ArrayList<String>(1);
			single.add(str[0] + "");
			return single;
		}
		
		List<String> results = new ArrayList<String>();	
		for (char character : str) {
			char[] others = getOtherCharacters(character, str);
			List<String> subResults = permutations(others);
			for (String subResult : subResults) {
				results.add(character + subResult);
			}
		}
		
		return results;
	}

	private char[] getOtherCharacters(char charShouldBeRemoved, char[] str) {
		char[] copy = new char[str.length - 1];
		int indexOfCopy = 0;
		for (int i = 0; i < str.length; i++) {
			if (str[i] == charShouldBeRemoved) continue;
			copy[indexOfCopy++] = str[i];
		}
		return copy;
	}

	public static void main(String[] args) {
		StringPermutations sp = new StringPermutations();

        long start = System.currentTimeMillis();
		List<String> results = sp.permutations("abcdefg".toCharArray());
		int i = 1;
		for (String result : results) {
			System.out.println(i++ + ": " + result);
		}
        System.out.println(System.currentTimeMillis() - start);
	}
}
